package com.lc.lc451;

import java.util.*;

public class Main {

}

class Solution {
    public String frequencySort(String s) {
        char[] p = s.toCharArray();
        
        Map<Character, Integer> mp = new HashMap<Character, Integer>();
        
        int n = p.length;
        for (int i = 0; i < n; i ++) {
        	mp.put(p[i], mp.getOrDefault(p[i], 0) + 1);
        }
        
        List<Character> t = new ArrayList<>(mp.keySet());
        
        t.sort(new Comparator<Character>() {
			@Override
			public int compare(Character o1, Character o2) {
				return mp.get(o2) - mp.get(o1);
			}
		});
        
        StringBuilder stringBuilder = new StringBuilder();
        for (char c : t) {
        	for (int j = 0; j < mp.get(c); j ++) {
        		stringBuilder.append(c);
        	}
        }
        return stringBuilder.toString();
    }
}